1. Field of the Invention
The present invention relates to the field of digital transmission through analog channels and, more particularly, to a method and apparatus for calculating metrics in a maximum likelihood detector for decoding a sequence of signals received through analog channels.
2. Background Art
Communication of voice and data signals is often accomplished by converting analog signals to digital signals. These digital signals are then transmitted from a transmitting device to a receiving device, converted back to analog signals, if necessary, and subsequently communicated to a user. This type of digital transmission is often performed through analog transmission channels. Digital information through this analog channel is transmitted in the form of "symbols" representing digital values. In some cases, adjacent symbols can overlap, resulting in a phenomenon known as intersymbol interference. This interference may corrupt a digital transmission, leading to errors in the receipt of the digital information.
These types of errors in transmission of digital information occur in many instances, including in magnetic recording channels. Such channels may suffer from intersymbol interference as well as noise present during transmission, and therefore require a method for decoding the binary symbol sequences that they output in a possibly corrupted form. Those skilled in the art are familiar with a decoding technique called maximum likelihood sequence estimation (MLSE), which is an effective tool used in conjunction with pulse detectors for receiving and decoding digital transmissions that suffer from intersymbol interference and noise. Maximum likelihood detection is especially useful with partial response signaling, for example class IV partial response signaling, in which the ideal response of a magnetic recording channel is modeled. Using the idealized response, and accounting for the effects of noise, maximum likelihood detection retrospectively analyzes received signals and determines the most likely sequence of data transmitted through the magnetic recording channel.
Class IV partial response signaling is only one type of partial response signaling currently used. In a class IV partial response, or PR4 system, when a pulse indicating a single magnetization transition occurs, it will ideally result in an impulse equal to "1" at the transition location and another impulse at the next sample period. The second impulse is equivalent to a response given by the operator (1+D). PR4 is a particular case of a more general family of PR polynomials, given by the general equation: (1-D)(1+D).sup.n. PR4 corresponds to n=1. Another system, called EPR4, or "Enhanced Partial Response 4," is provided by setting n=2. In the EPR4 system, the impulse response caused by an isolated transition in a magnetic recording channel may be approximated by the term (1+D).sup.2 =1+2D+D.sup.2. When n=3, the impulse response is given by the polynomial (1+D).sup.3 =1+3D+3D.sup.2 +D.sup.3. This type of partial response is called E.sup.2 PR4. Because E.sup.2 PR4 is a higher order polynomial, it provides the closest fit to the magnetic channel frequency response, and is therefore a better predictor of the actual response of the magnetic channel. An embodiment of a metric calculator according to the present invention is disclosed with respect to the EPR4 system. However, it will be understood by those skilled in the art that the invention can also be applied to other systems, including PR4 and E.sup.2 PR4 systems.
Various implementations of maximum likelihood sequence estimation, in particular, the Viterbi algorithm, are well known in the art. Several of these implementations are discussed in U.S. Pat. No. 5,384,560, assigned to the assignee of the present application. A brief explanation of the EPR4 Viterbi detector is given here to facilitate the explanation of the present invention. A more complete explanation of the EPR4 Viterbi detector is provided in G. David Forney, Jr., "Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interferences," IT-18 IEEE Transactions on Information Theory, 363 (May 1972), incorporated herein by reference.
The EPR4 Viterbi detector is a sequence detector for a signal channel whose response is characterized by the following EPR4 equation: EQU (1-D)(1+D).sup.2 =(1-D)(1+2D+D.sup.2),
where D is a delay operator representing one unit of delay or code period Tc. Using this equation, the Viterbi detector attempts to derive data that it computes to be most likely from a sequence of received signals.
The EPR4 channel is completely characterized by transitions associated with three binary bits: the current data bit (I.sub.k), one bit just prior to it Ik-1, and another bit that is two code periods (2Tc) earlier Ik-2. It will be apparent to these skilled in the art that these three binary bits (Ik, Ik-1, Ik-2) fully describe one of the eight states in which the channel can be at time k. The EPR4 Viterbi detector assigns a measure of likelihood to all eight states at every code period, and derives data from the state that is determined to be most likely. As is known in the art, the value that is computed as a measure of likelihood is called a metric.
FIGS. 1(a)-1(d) are timelines illustrating a simple example of an EPR4 channel response. In the timeline shown in FIG. 1(a), the signal Iw represents a sequence of binary data input to the EPR4 channel. This signal can represent an input sequence 0011000, for example, after the data is processed in a read channel circuit and output as the current of a write flip flop circuit. At time k, the write current transitions from one to zero, or from high to low. In the ideal case where there is no noise, this transition generates an overall EPR4 response of X.sub.k =0, shown at time=k in FIG. 1(d).
The timeline in FIG. 1(b) illustrates the (1-D) response to signal Iw, representing the differentiation process associated with the magnetic transition caused by the write current Iw onto the media.
The timeline in FIG. 1(c) is the PR4 response of the channel characterized by the multiplication of an additional (1+D) operator to the (1-D) differentiation signal. As can be seen from the figure, this is equivalent to time-shifting the (1-D) response by a unit delay, and adding the result to the (1-D) response. This function approximates the "spreading" of the magnetic transition of the FIG. 1(a) timeline over neighboring bit periods in a PR4 system.
Finally, the timeline in FIG. 1(d) shows the EPR4 response, which is obtained by further multiplying the PR4 response with yet another (1+D) operator. This response characterizes the response of the EPR4 channel for the signal shown in the FIG. 1(a) timeline. As can be seen from FIGS. 1(a) and 1(d), the ideal overall EPR4 response of X.sub.k, in the absence of noise, for a transition from state "3" (011) to state "6" (011), at time k, is equal to zero.
FIGS. 2(a)-2(d) are timelines illustrating another simple example of an EPR4 channel response. In the timeline shown in FIG. 2(a), the signal Iw represents binary data input sequence of 0111000, outputted as current by the output of a flip flop in a read channel. As in FIG. 1(b), the timeline in FIG. 2(b) illustrates the (1-D) differentiation response to signal Iw. The timeline in FIG. 2(c) illustrates the PR4 response of the channel characterized by the multiplication of an additional (1+D) operator to the (1-D) differentiation signal. Finally, the timeline in FIG. 2(d) shows the EPR4 response for 0111000, obtained by further multiplying the PR4 response with another (1+D) operator.
As in FIG. 1(a), the timeline in FIG. 2(a) shows the write current transitioning from one to zero at time=k. However, the transition of the signal from state "7" or 111, to state "3" or 110, generates an ideal overall EPR4 response of x.sub.k =-1, shown at time=k in FIG. 2(d).
The ideal characteristic responses of the EPR4 channel in these examples can be used to derive metric equations for the different states of the channel. With reference to FIGS. 1(a) and 1(d), for example, at time=k, with no noise present, the ideal response of the channel is x.sub.k =0 and the channel is in state "6" or 110 in binary (with Ik-2, Ik-1 Ik=1,1,0). In the presence of noise, the response changes from x.sub.k to the actual response, y.sub.k. We can determine the likelihood of the channel being in the state "6" at time (t)=k as follows. To come to the state "6 "=110, the previous channel state (I.sub.k-3, I.sub.k-2, I.sub.k-1) had to be either 011="3" or 111="7." Thus the metric calculator will limit itself to these two possibilities of what the previous channel could have been. This two-way decision approach is often called the "Radix 2" approach.
For the possibility that the previous channel state was "3," as shown in FIG. 1(a), the actual response is y.sub.k =x.sub.k +n.sub.k, where n.sub.k represents noise present in the actual response y.sub.k sample. As discussed above and shown in FIG. 1(d), the ideal response xk is equal to zero for the transition from "3" to "6." Therefore, if the previous channel state was "3," the actual response y.sub.k =0+n.sub.k =n.sub.k. However, if the previous channel state was "7," the response would be y.sub.k =-1+n.sub.k. This is shown in FIG. 2(d), where the ideal response, x.sub.k, for the transition from previous state "7" to current state "6" is equal to -1.
To determine which of the two previous states, "3" or "7," is most likely the correct state, we determine which transition to "6" results in the smallest error from the ideal response of the EPR4 channel. To achieve this, we compute mean square errors for the two possible states, as follows:
For the case of a transition from "3" to "6" with x.sub.k =0, the mean square error=(y.sub.k -x.sub.k).sup.2 =(y.sub.k -0).sup.2 =y.sub.k.sup.2.
For the case of a transition from "7" to "6" with x.sub.k =-1, the mean square error (y.sub.k -x.sub.k).sup.2 =(y.sub.k -(-1)).sup.2 =y.sub.k.sup.2 +2y.sub.k +1.
Since y.sub.k.sup.2 is common to both mean square errors, it can be eliminated from the metric calculations. The smallest mean square error is chosen, indicating the state most likely correct (i.e., the state most likely to have been the state previous to "6"). Therefore, in our example, if 2y.sub.k +1 is greater than zero, then the selected state will be "3," or 001, and the data bit three units prior in time will have been 0. If, however, 2y.sub.k +1 is less than zero, the selected state will be "7," or 111, and the data bit three units prior in time will have been 1. In the case where 2y.sub.k +1 is equal to zero, meaning the likelihood of previous states "3" and "7" is the same, the state "3" can be selected to permit calculations to proceed.
It is often easier in circuit implementations to compute a maximum value rather than a minimum value. Therefore, the equations above are normalized and simplified by dividing through by -2 and adding a constant term "0.5" to both equations. Thus, a metric value at time k is derived for state "6" as follows: M.sub.k (6)=Max{M.sub.k-1 (3)+0.5, M.sub.k-1 (7)-y.sub.k }. This equation states that the likelihood of state "6" at time k is assigned a value which is the larger of the previous metric associated with state "3" plus a constant term of "0.5," or of the previous metric associated with state "7" minus the received sample y.sub.k. If the former is chosen then the decision I.sub.k-3 is 0 since the previous state was 011="3". Otherwise, the decision is 1 from 111="7". Note that the decision made at k is for I.sub.k-3 and has three code periods delay associated with it.
Similarly, for the remaining seven states after similar manipulations we have the following equations. The equation for state "6" given above is included for completeness: EQU M.sub.k (0)=Max{M.sub.k-1 (0)+0.5, M.sub.k-1 (4)-y.sub.k }, EQU M.sub.k (1)=Max{M.sub.k-1 (0)+y.sub.k, M.sub.k-1 (4)+0.5}, EQU M.sub.k (2)=Max{M.sub.k-1 (1)+y.sub.k, M.sub.k-1 (5)+0.5}, EQU M.sub.k (3)=Max{M.sub.k-1 (1)+2y.sub.k -1.5, M.sub.k-1 (5)+y.sub.k }, EQU M.sub.k (4)=Max{M.sub.k-1 (2)-y.sub.k, M.sub.k-1 (6)-2y.sub.k -1.5}, EQU M.sub.k (5)=Max{M.sub.k-1 (2)+0.5, M.sub.k-1 (6)-y.sub.k }, EQU M.sub.k (6)=Max{M.sub.k-1 (3)+0.5, M.sub.k-1 (7)-y.sub.k }, EQU M.sub.k (7)=Max{M.sub.k-1 (3)+y.sub.k, M.sub.k-1 (7)+0.5},
The above computations, algebraically manipulating previous metrics to provide current values of metrics, are called ACS computations since they involve an Add, Compare and Select process. At the end of every code period, every state has a metric value, indicating the likelihood that the channel is in that state. In addition, every state has a sequence of decisions associated with itself. Eight sets of these data are then fed into a register called the "survival path register." This register performs the final selection of data, I.sub.k-3, with some further delay that is dependent on the particulars of the survival path register implementation chosen. As will be recognized by those skilled in the art, the object of all survival path registers, whatever their implementation, is to pick the most likely sequence among the eight possible candidates.
FIG. 3 is a state transition diagram. As its name implies it simply shows the history of state transitions from one code period to the next. Such diagrams are often used to describe Viterbi path "merge." If the survival path register is sufficiently long, the path will tend to "merge," i.e., all eight decisions tend to be identical, making the particular state from which data is chosen unimportant. The particulars of survival path registers are not important and the implementation is always digital.
The prior art has most commonly implemented Viterbi detectors in the digital domain after A/D conversion. Such implementations may result in loss of performance, loss of achievable data rate, or both. A very straightforward analog approach would be to attempt the above-described ACS computations in one period, Tc. However, this approach does not lend itself to the data rate requirement of current HDDS.
To overcome the speed limitation of the one-step approach, another conceivable analog implementation would be to use a two-step approach illustrated in FIGS. 4(a) and 4(b). With this approach, ACS computations would be carried out in two code periods, or 2Tc. For example, as shown in FIG. 4(a), instead of determining path metrics for the transition in one code period from "3" to "6" and "7" to "6," as before, path metrics would be calculated for the transitions from "1" to "3" to "6," "5" to "3" to "6," "3" to "7" to "6" and "7" to "7" to "6." This approach necessarily increases speed at the expense of hardware complexity. Instead of making the two-way decision as described above, a four-way decision would be performed at every other code period (Radix 4). Using this approach, the metric update equations for state "i" become: EQU M.sub.k (i)=Max{M.sub.k-1 (j)+etc.,M.sub.k-1 (k)+etc.} EQU =Max{Max{M.sub.k-2 (l)+etc., M.sub.k-2 (m)+etc.},Max(M.sub.k-2 (n)+etc., M.sub.k-2 (o)+etc.}} EQU =Max{M.sub.k-2 (l)+etc., M.sub.k-2 (m)+etc., M.sub.k-2 (n)+etc., M.sub.k-2 (o)+etc.}.
Here states j and k are two possible states at time k-1 from which state "i" could have come. States I and m, and n and o, are four possible states at time k-2 from which states j and k respectively, could have come. For example, for "i "=6=110, the metric equations become: EQU M.sub.k (6)=Max{M.sub.k-1 (3)+0.5, M.sub.k-1 (7)-y.sub.k } EQU =Max{Max{M.sub.k-2 (1)+2y.sub.k-1 -2.5, M.sub.k-2 (5)+y.sub.k-1 },Max{M.sub.k-2 (3)+y.sub.k-1, M.sub.k-2 (7)+0.5}}. EQU =Max{M.sub.k-2 (1)+2y.sub.k-1 -2.5, M.sub.k-2 (5)+y.sub.k-1, M.sub.k-2 (3)+y.sub.k-1, M.sub.k-2 (7)+0.5}.
Thus (j,k) are 3=011 and 7=111 and (l,m) and (n,o) are 001="1," 101="5," and 011="3," and 111="7." Associated decisions, I.sub.k-4, I.sub.k-3, are 00,10,01,11 for states "1," "5," "3" and "7," respectively.
Thus, the two step approach requires Additions involving two past samples, y.sub.k, y.sub.k-1, Comparisons of four metrics and Selections of the largest metric out of the four. FIG. 4(b) is a block diagram illustrating this two-step approach, and a timing diagram therefor. Two samples, y.sub.k, and also y.sub.k-1, are inputted to a detector such that four metrics are calculated and the largest metric, M.sub.k, is stored by capacitors CHA and CHB alternately. The selection process of the largest metric also yields the decisions. The metric calculations must be done in two code periods, for example 10 nanoseconds in the example of FIG. 4(b). While this implementation would still present a workable approach, it is complex and the hardware required to realize it would be very costly, not only in terms of silicon area, but also in terms of matching of components needed to achieve near-ideal performance.